class Solution {
public:
    ListNode *reverse(ListNode *pNode)
    {
        ListNode *p1;
        ListNode *p2 = NULL;
        while(pNode) {
            p1 = pNode->next;
            pNode->next = p2;
            p2 = pNode;
            pNode = p1;
        }
        return p2;
    }

    bool isPalindrome(ListNode *head)
    {
        ListNode *p = head;
        int len = 0, t = 0;
        if(!head){
            return true;
        }
        while(p) {
            len++;
            p = p->next;
        }
        p = head;
        if(len % 2) {
            t = len / 2 + 1;
        } else {
            t = len / 2;
        }
        while(t--) {
            p = p->next;
        }

        p = reverse(p);

        while(head && p) {
            if(head->val != p->val) {
                return false;
            }
            head = head->next;
            p = p->next;
        }
        return true;
    }
};